package everyday;

import common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangmin
 * @create 2022-05-03 9:45
 * 打家劫舍3
 * 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
 * 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
 * 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
 *
 * 思路：递归
 * 记录达到每个节点时候的最大金额
 *
 */
public class rob337 {
    Map<TreeNode,Integer> memo=new HashMap<>();
    public int rob(TreeNode root) {
        if (root==null) return 0;
        if (memo.containsKey(root)) return memo.get(root);
        int do_it=root.val+(root.left==null?0:(rob(root.left.left)+rob(root.left.right)))+
                (root.right==null?0:(rob(root.right.left)+rob(root.right.right)));
        int not_do=rob(root.left)+rob(root.right);
        int res=Math.max(do_it,not_do);
        memo.put(root,res);
        return res;
    }
}
